SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Memory-bound function</title>

</head>

Memory-bound function

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

Memory bound refers to a situation in which the time to complete a given <a href="Computational_problem" title="Computational problem">computational problem</a> is decided primarily by the amount of free <a href="Computer_memory" title="Computer memory">memory</a> required to hold the working <a href="Data" title="Data">data</a>. This is in contrast to algorithms that are <a href="Compute-bound" class="mw-redirect" title="Compute-bound">compute-bound</a>, where the number of elementary computation steps is the deciding factor.

Memory and computation boundaries can sometimes be traded against each other, e.g. by saving and reusing preliminary results or using <a href="Lookup_table" title="Lookup table">lookup tables</a>.

<div class="mw-heading mw-heading2"><h2 id="Memory-bound_functions_and_memory_functions">Memory-bound functions and memory functions</h2></div>

Memory-bound <a href="Subroutine" class="mw-redirect" title="Subroutine">functions</a> and memory functions are related in that both involve extensive memory access, but a distinction exists between the two.

Memory functions use a <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> technique called <a href="Memoization" title="Memoization">memoization</a> in order to relieve the inefficiency of <a href="Recursion" title="Recursion">recursion</a> that might occur. It is based on the simple idea of calculating and storing solutions to subproblems so that the solutions can be reused later without recalculating the <a href="Optimal_substructure" title="Optimal substructure">subproblems</a> again. The best known example that takes advantage of memoization is an <a href="Algorithm" title="Algorithm">algorithm</a> that computes the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a>. The following <a href="Pseudocode" title="Pseudocode">pseudocode</a> uses recursion and memoization, and runs in <a href="Linear_time" class="mw-redirect" title="Linear time">linear CPU time</a>:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> Fibonacci (n)

{

for i = 0 to n-1

results[i] = -1 // -1 means undefined

return Fibonacci_Results (results, n);

}

Fibonacci_Results (results, n)

{

if (results[n] != -1) // If it has been solved before,

return results[n] // look it up.

if (n == 0)

val = 0

else if (n == 1)

val = 1

else

val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)

results[n] = val // Save this result for re-use.

return val

}

</pre></div>

Compare the above to an algorithm that uses only recursion, and runs in <a href="Exponential_time" class="mw-redirect" title="Exponential time">exponential</a> CPU time:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> Recursive_Fibonacci (n)

{

return 0

return 1

return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)

}

</pre></div>

While the recursive-only algorithm is simpler and more elegant than the algorithm that uses recursion and memoization, the latter has a significantly lower <a href="Time_complexity" title="Time complexity">time complexity</a> than the former.

The term "memory-bound function" has only come into use relatively recently, and is used principally to describe a function that uses XOR and consists of a series of computations in which each computation depends on the previous computation. Memory functions have long been an important tool used to improve time complexity, but memory-bound functions have seen far fewer applications.

<div class="mw-heading mw-heading2"><h2 id="Using_memory-bound_functions_to_prevent_spam">Using memory-bound functions to prevent spam</h2></div>

Memory-bound functions might be useful in a <a href="Proof_of_work" title="Proof of work">proof-of-work system</a> that could deter <a href="Spamming" title="Spamming">spam</a>, which has become a problem of epidemic proportions on the <a href="Internet" title="Internet">Internet</a>.

In 1992, IBM research scientists <a href="Cynthia_Dwork" title="Cynthia Dwork">Cynthia Dwork</a> and <a href="Moni_Naor" title="Moni Naor">Moni Naor</a> published a paper at CRYPTO 1992 titled Pricing via Processing or Combatting Junk Mail,<a href="#cite_note-1">[1]</a> suggesting a possibility of using <a href="CPU-bound" title="CPU-bound">CPU-bound</a> functions to deter abusers from sending spam. The scheme was based on the idea that computer users are much more likely to abuse a resource if the cost of abusing the resource is negligible: the underlying reason spam has become so rampant is that sending an <a href="E-mail" class="mw-redirect" title="E-mail">e-mail</a> has minuscule cost for spammers.

Dwork and Naor proposed that spamming might be reduced by injecting an additional cost in the form of an expensive <a href="CPU" class="mw-redirect" title="CPU">CPU</a> computation: CPU-bound functions would consume CPU resources at the sender's machine for each message, thus preventing huge amounts of spam from being sent in a short period.

The basic scheme that protects against abuses is as follows:

Given a Sender, a Recipient, and an email Message. If Recipient has agreed beforehand to receive e-mail from Sender, then Message is transmitted in the usual way. Otherwise, Sender computes some function G(Message) and sends (Message, G(Message)) to Recipient. Recipient checks if what it receives from Sender is of the form (Message, G(Message)). If yes, Recipient accepts Message. Otherwise, Recipient rejects Message.

The function G() is selected such that the verification by Recipient is relatively fast (e.g., taking a millisecond) and such that the computation by Sender is somewhat slow (involving at least several seconds). Therefore, Sender will be discouraged from sending Message to multiple recipients with no prior agreements: the cost in terms of both time and computing resources of computing G() repeatedly will become very prohibitive for a spammer who intends to send many millions of e-mails.

The major problem of using the above scheme is that fast CPUs compute much faster than slow CPUs. Further, higher-end computer systems also have sophisticated pipelines and other advantageous features that facilitate computations. As a result, a spammer with a state-of-the-art system will hardly be affected by such deterrence while a typical user with a mediocre system will be adversely affected. If a computation takes a few seconds on a new <a href="Personal_computer" title="Personal computer">PC</a>, it may take a minute on an old PC, and several minutes on a <a href="Personal_digital_assistant" title="Personal digital assistant">PDA</a>, which might be a nuisance for users of old PCs, but probably unacceptable for users of PDAs. The disparity in client CPU speed constitutes one of the prominent roadblocks to widespread adoption of any scheme based on a CPU-bound function. Therefore, researchers are concerned with finding functions that most computer systems will evaluate at about the same speed, so that high-end systems might evaluate these functions somewhat faster than low-end systems (2–10 times faster, but not 10–100 times faster) as CPU disparities might imply. These ratios are "<a href="Egalitarian" class="mw-redirect" title="Egalitarian">egalitarian</a>" enough for the intended applications: the functions are effective in discouraging abuses and do not add a prohibitive delay on legitimate interactions, across a wide range of systems.

The new egalitarian approach is to rely on memory-bound functions. As stated before, a memory-bound function is a function whose computation time is dominated by the time spent accessing memory. A memory-bound function accesses locations in a large region of memory in an unpredictable way, in such a way that using caches are not effective. In recent years, the speed of CPU has grown drastically, but there has been comparatively small progress in developing faster main memory. Since the <a href="Ratio" title="Ratio">ratios</a> of <a href="Memory_latency" title="Memory latency">memory latencies</a> of machines built in the last five years is typically no greater than two, and almost always less than four, the memory-bound function will be egalitarian to most systems for the foreseeable future.

<ul><li><a href="Computer_architecture" title="Computer architecture">Computer architecture</a></li>

<li><a href="CPU-bound" title="CPU-bound">CPU-bound</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="I/O_bound" title="I/O bound">I/O-bound</a></li>

<li><a href="Memoization" title="Memoization">Memoization</a></li>

<li><a href="Memory-hard_function" title="Memory-hard function">Memory-hard function</a></li>

<li><a href="Optimal_substructure" title="Optimal substructure">Optimal substructure</a></li>

<li><a href="Proof_of_work" title="Proof of work">Proof of work</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Memory_bottleneck" class="mw-redirect" title="Memory bottleneck">Memory bottleneck</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDworkNaor1992" class="citation book cs1"><a href="Cynthia_Dwork" title="Cynthia Dwork">Dwork, Cynthia</a>; <a href="Moni_Naor" title="Moni Naor">Naor, Moni</a> (1992). <a rel="nofollow" class="external text" href="https://www.iacr.org/cryptodb/data/paper.php?pubkey=1268">"Pricing via Processing or Combatting Junk Mail"</a>. Advances in Cryptology — CRYPTO' 92. Lecture Notes in Computer Science. Vol. 740. pp. 139–147. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-48071-4_10">10.1007/3-540-48071-4_10</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-57340-1</bdi>.</cite> (<a rel="nofollow" class="external text" href="http://www.wisdom.weizmann.ac.il/~naor/PAPERS/pvp.pdf">updated version of same</a>)

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li>Abadi, M., Burrows, M., Manasse, M., & Wobber, T. (2005, May). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/wp-content/uploads/2005/05/memory-longer-acm.pdf">Moderately Hard, Memory-bound Functions</a>, ACM Transactions on Internet Technology.</li>

<li>Dwork, C., Goldberg, A., & Naor, M. (2003). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/wp-content/uploads/2003/08/crypto03.pdf">On Memory-Bound Functions for Fighting Spam</a>, Advances in Cryptology.</li>

<li>Hellman, M. E. (1980). <a rel="nofollow" class="external text" href="https://ee.stanford.edu/~hellman/publications/36.pdf">A Cryptanalytic Time-Memory Trade Off</a>, IEEE Transactionson Information Theory.</li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://pennypost.sourceforge.net/MBound">Implementation of a Memory Bound function</a></li>

<li><a rel="nofollow" class="external text" href="http://web.cs.iastate.edu/~prabhu/Tutorial/title.html">Computer Architecture</a></li>

<li><a rel="nofollow" class="external text" href="https://computer.howstuffworks.com/computer-memory.htm">How Computer Memory Works</a></li>

<li><a rel="nofollow" class="external text" href="https://mat.gsia.cmu.edu/classes/dynamic/dynamic.html">Dynamic Programming</a></li>

<li><a rel="nofollow" class="external text" href="http://allendowney.com/cs357spring1998/ass5/node6.html">CPU Bound vs. I/O Bound</a></li>

<li><a rel="nofollow" class="external text" href="https://www.consumer.ftc.gov/articles/0038-spam">Spam – FTC Consumer Information</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-13" href="https://en.wikipedia.org/wiki/?title=Memory-bound_function&oldid=1300218925">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>